#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define vec vector<int>
#define y1 y_____hahahaha_____1

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * sgn;}

const int N = 2e3+10;

int mod,n;
int f[N][N],g[N][N];

int upd(int x){return x + (x >> 31 & mod);}

void solve(){
	n = in,mod = in;
	for(int i = 0;i <= n * 2;i++) for(int j = 0;j <= i / 2;j++) f[i][j] = 0,g[i][j] = 0;
	f[1][0] = 1;
	for(int i = 2;i <= n * 2;i++){
		f[i][0] = 1;
		for(int j = 1;j <= i / 2;j++){
			if(i != n * 2 && j * 2 == i) continue; int lef = i - 2 * j + 1;
			f[i][j] = upd(f[i-1][j] + (ll)f[i-1][j-1] * lef % mod - mod);
			g[i][j] = upd(g[i-1][j] + (ll)g[i-1][j-1] * lef % mod - mod);
			g[i][j] = upd(g[i][j] + (ll)f[i-1][j-1] * (lef * (lef - 1) / 2 % mod) % mod - mod);
		}
	}
	printf("%d\n",g[2 * n][n]);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	for(int t = in;t;t--) solve();
	return 0;
}
